iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 1
1
Software Development

LeetCode30系列 第 1

[LeetCode30] Day1 - 前言 (還是有一題啦 顆顆)

  • 分享至 

  • xImage
  •  

動機?

看同隊的都先打動機,那我就也模仿一下,反正也沒為什麼,同學缺人,就加啦!

看這文章能學到什麼?

leetcode有3個等級的難度:Easy, Medium, Hard,會各10題。
我只能說不好說,因為隨便挑題,可能會學到一些基本的資料結構或演算法,也可能不小心挑到兩數字和這種簡單的題目,造成你感到會覺得很廢,但我會努力的。
之後都是會先講講一些概念,然後各種解法,主要用C++。

進入正題吧 26. Remove Duplicates from Sorted Array

題目

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

概念

in-place update 和out of place update的差別

in-place 即是將更新的資料寫入相同的記憶體位址上。
out of place 即是將更新的資料寫入到別的記憶體位址上。

解法

在C++的話,輸入參數是vector,能使用vector的erase,那很直觀的,我們就從第一個數字開始與下個數字比較,重複則刪除,直到不一樣為止,在以下個數字重複這件事。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {   
        int i = 1;
        
        while(i < nums.size()){
            if(nums[i] == nums[i-1]){
                nums.erase(nums.begin()+i-1);
            }
            else{
                i++;
            }
        }
        
        return nums.size();
    }
};

但是用直接用erase非常的低效,因為erase會把後面的數字都往前搬移。
https://ithelp.ithome.com.tw/upload/images/20200916/20129147LEmawsJrWZ.png

所以使用2個變數當作旗標(如下的i和j), j指著當前數字,i則指著下個數字,一樣做比較,但重複不刪除,直接跳過,直到不同再更新。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 1) {
            return nums.size();
        }
        
        int size = 0;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] != nums[size]) {
                nums[++size] = nums[i];
            }
        }

        return size + 1;
    }
};

https://ithelp.ithome.com.tw/upload/images/20200916/201291472HoELOrF5J.png
這樣就能提高效能囉!
今天就先這樣,拜拜!


下一篇
[LeetCode30] Day2 - 461. Hamming Distance
系列文
LeetCode3030
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言